package 面试.遍历算法;

public class 希尔排序 {
    public static void main(String[] args) {
        int[] arr = {7,4,3,9,6,5,3,4,21,23,52,12,86,23,34,15,25,16,867,92,82,223,123,556,234,12356,21312,643,12312,645,32421,12334,324,21,34,153,123312,42342};

        long start = System.currentTimeMillis();
        int gap = arr.length;
        while (gap > 1){//gap = 1,是最后遍历的次数，此时与插入排序无区别
            gap /= 2;// gap除2先进行粗略的插入排序
            for (int i = 0; i < arr.length-gap; i++) {//因为比较的是前面的数组内容，所以遍历范围为数组长度减gap值
                int num = arr[i+gap];//该值表示要往前插入的数
                int j = i;//该值表示从哪里开始往前遍历
                while (arr[j] > num){
                    arr[j+gap] = arr[j];
                    j -= gap;
                    if (j < 0) break;
                }
                //走到这里有两种可能，一种是遍历到头了
                //一种是遍历找到对应的插入位置
                arr[j + gap] = num;
            }
        }
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        System.out.println(arr.length);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
